<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            LeetCode背包问题 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">LeetCode背包问题</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2019-11-29 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/LeetCode/">LeetCode</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E8%83%8C%E5%8C%85/">背包</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>9.4k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>43 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <blockquote>
<p>从<a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/">动态规划专题</a> 中抽取出来的</p>
</blockquote>
<h2 id="92-背包问题（lintCode）"><a href="#92-背包问题（lintCode）" class="headerlink" title="92.背包问题（lintCode）"></a><a class="link"   target="_blank" rel="noopener" href="https://www.lintcode.com/problem/backpack/description" >92.背包问题（lintCode）<i class="fas fa-external-link-alt"></i></a></h2><p>在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]</p>
<ul>
<li>你不可以将物品进行切割</li>
</ul>
<p><strong>样例</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">样例 <span class="number">1</span>:</span><br><span class="line">	输入:  [<span class="number">3</span>,<span class="number">4</span>,<span class="number">8</span>,<span class="number">5</span>], backpack size=<span class="number">10</span></span><br><span class="line">	输出:  <span class="number">9</span></span><br><span class="line">样例 <span class="number">2</span>:</span><br><span class="line">	输入:  [<span class="number">2</span>,<span class="number">3</span>,<span class="number">5</span>,<span class="number">7</span>], backpack size=<span class="number">12</span></span><br><span class="line">	输出:  <span class="number">12</span></span><br></pre></td></tr></table></figure>

<p><strong>挑战</strong></p>
<ul>
<li><p>O(n x m) time and O(m) memory.</p>
</li>
<li><p>O(n x m) memory is also acceptable if you do not know how to optimize memory.</p>
</li>
</ul>
<p><strong>解法一</strong></p>
<p>记忆化递归，对于每个元素，有两种选择，装或者不装</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//用Integer[][],空间会超空间。。。lintCode好严格</span></span><br><span class="line"><span class="keyword">int</span> [][] cache=<span class="keyword">null</span>;    </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">backPack2</span><span class="params">(<span class="keyword">int</span> m,<span class="keyword">int</span>[] A)</span> </span>&#123;</span><br><span class="line">    cache=<span class="keyword">new</span> <span class="keyword">int</span>[A.length+<span class="number">1</span>][m+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;A.length;i++) &#123;</span><br><span class="line">        Arrays.fill(cache[i],-<span class="number">1</span>);   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (A==<span class="keyword">null</span> || A.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> putPack(m,A,A.length-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//将A[index,A.len-1]范围内的元素装进大小为m的背包的最大收益</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">putPack</span><span class="params">(<span class="keyword">int</span> m,<span class="keyword">int</span>[] A,<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//index==0的时候不应该返回=0代表第一个,是可以装的</span></span><br><span class="line">    <span class="comment">//对于m也是一样, 这种边界思考一下m就等于0，或者就只有一个元素，index就等于0这种特例就可以</span></span><br><span class="line">    <span class="comment">//只要这种特例是正确的那么整个递归就是正确的,并不需要去思考整个递归的结束条件</span></span><br><span class="line">    <span class="keyword">if</span> (index&lt;<span class="number">0</span> || m&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (cache[index][m]!=-<span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[index][m];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//不装index位置的元素</span></span><br><span class="line">    <span class="keyword">int</span> res=putPack(m,A,index-<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">if</span> (A[index]&lt;=m) &#123;</span><br><span class="line">        <span class="comment">//说明可以装下index位置的元素，所以我们将index位置的元素装进去试试看</span></span><br><span class="line">        <span class="comment">//然后求出剩下的空间还最多能装多少，最后求是装index收益大还是不装index收益大</span></span><br><span class="line">        res=Math.max(res,A[index]+putPack(m-A[index],A,index-<span class="number">1</span>));</span><br><span class="line">    &#125;</span><br><span class="line">    cache[index][m]=res;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>暴力递归的时间复杂度将会是<code>O((2^N)*N)</code></p>
<p>其实整个递归的思路是很清晰明白的，对于每个元素，有两种情况，这也是之所以称之为0-1背包的原因</p>
<ul>
<li>不选的话，背包的容量不变，改变为问题<code>putPack(m,A,index-1)</code></li>
<li>选的话，背包的容量变小，改变为问题<code>putPack(m-A[index],A,index-1)+A[index]</code></li>
</ul>
<p>到底选还是不选，取决于两种方案哪一种更好，我们要求的，就是这个最好的方案，知道了这样的递推关系后我们就可以很容易的写出递归方程，这里在递归的过程中有可能会产生重叠的子问题（其实这里我还纠结了好一会儿，我一直感觉没有重叠的子问题，后来画一下递归树就明白了，只是重叠的不明显），所以我们可以通过缓存每次计算的结果来进行记忆化递归，整体的时间复杂度应该是<code>O(2^N)</code>，空间<code>O(M*N)</code>显然不是我们想要的结果</p>
<blockquote>
<p>这里一开始我是想用<code>Integer[][]</code>的数组，然后就不用赋初始值，判断不为null就行，结果空间溢出了。。。lintCode好严格，换成<code>int[][]</code>然后赋个初始值就过了</p>
</blockquote>
<p><strong>解法二</strong></p>
<p>动态规划解法，在讲解之前，我们用一个二维表来分析下整个递推的过程</p>
<p>物品列表（样例1），因为这题价值就是重量，所以w和v是一样的</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200227/XIvS0eAf1FqA.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>DpTable（样例1）</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200227/YkPisR3fx1wa.png?imageslim"
                      alt="mark"
                ></p>
<p>一行一行的看，从左到右，<code>dp[index][m]</code>代表 <strong>背包总容量不超过m的情况下，考虑装入<code>[0,index]</code>中的元素能获得最大收益</strong>，比如<code>dp[1][7]</code>代表的就是背包总容量不超过7的情况下，考虑装入<code>[0,1]</code> 范围内的元素所能获得的最大收益，人脑思考结果自然是7了，下面我们分析下如果dp推出这个结果</p>
<p>前面我们已经分析过0-1背包的递归过程，每个元素面临两个选择，这里也一样</p>
<p><code>dp[1][7]</code>如果我们选择不装入当前index位置的元素的话，那么最大收益就是<code>dp[0][7]=3</code>这一点应该没啥疑问</p>
<p>如果我们考虑装入当前index位置的元素的话，m肯定会减小，那么所获得的最大收益就应该是<code>A[index]+dp[0][7-4]=7</code> </p>
<blockquote>
<p>注意这里当前index的值都是依赖于上一层<code>index-1</code>的计算结果的，也就是依赖于上一次<code>m,[0,index-1]</code>最大值的结果，所以我们需要手动的初始化第一层的值）</p>
</blockquote>
<p>最后我们得到的核心状态方程就是下面这样的</p>
<p><code>dp[index][m]=max(dp[index-1][m],A[index]+dp[index-1][j-A[index]])</code></p>
<p>然后我们根据这个很容易就可以写出dp的解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//二维动态规划</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">backPack</span><span class="params">(<span class="keyword">int</span> m,<span class="keyword">int</span>[] A)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (A==<span class="keyword">null</span> || A.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[][] dp=<span class="keyword">new</span> <span class="keyword">int</span>[A.length][m+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;A.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=m;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (j==<span class="number">0</span>) &#123;<span class="comment">//初始化第一列</span></span><br><span class="line">                dp[i][j]=<span class="number">0</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (i==<span class="number">0</span>) &#123;<span class="comment">//初始化第一行</span></span><br><span class="line">                dp[i][j]=j-A[i]&gt;=<span class="number">0</span>?A[i]:<span class="number">0</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (i&gt;<span class="number">0</span>) &#123;</span><br><span class="line">                dp[i][j]=j-A[i]&gt;=<span class="number">0</span>?Math.max(dp[i-<span class="number">1</span>][j],dp[i-<span class="number">1</span>][j-A[i]]+A[i]):dp[i-<span class="number">1</span>][j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[A.length-<span class="number">1</span>][m];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>当然我们肯定是不满足于这种二维的dp的，所以我们还得优化下空间，这里每一层都只依赖于上一层的结果，所以我么很容易就可以改成一维的，当然这里还有个小坑，如果直接按照上面的代码来改的话就是错的，我们先看看正确的改法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">backPack4</span><span class="params">(<span class="keyword">int</span> m,<span class="keyword">int</span>[] A)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (A==<span class="keyword">null</span> || A.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[m+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;A.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=m;j&gt;=<span class="number">0</span>;j--) &#123;<span class="comment">//从右向左，避免覆盖</span></span><br><span class="line">            <span class="keyword">if</span> (j==<span class="number">0</span>) &#123;<span class="comment">//初始化第一列</span></span><br><span class="line">                dp[j]=<span class="number">0</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (i==<span class="number">0</span>) &#123;<span class="comment">//初始化第一行</span></span><br><span class="line">                dp[j]= j-A[i]&gt;=<span class="number">0</span>?A[i]:<span class="number">0</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                dp[j]=j-A[i]&gt;=<span class="number">0</span>?Math.max(dp[j],dp[j-A[i]]+A[i]):dp[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[m];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以看到，我们的内层循环不再是从左往右，而是从右往左，这样的好处就是避免了<code>dp[j-A[i]]</code>已经被<strong>当前内层循环前面的元素</strong>覆盖的尴尬情况，结合上面的表推一下就知道了</p>
<p><strong>解法三</strong></p>
<p>算是对之前代码的优化吧，之前写的乱七八糟的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//代码优化</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">backPack</span><span class="params">(<span class="keyword">int</span> m,<span class="keyword">int</span>[] A)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (A==<span class="keyword">null</span> || A.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[m+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;A.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=m;j&gt;=A[i];j--) &#123;</span><br><span class="line">            dp[j]=Math.max(dp[j],dp[j-A[i]]+A[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[m];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="完全背包问题（acwing）"><a href="#完全背包问题（acwing）" class="headerlink" title="完全背包问题（acwing）"></a><a class="link"   target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/description/3/" >完全背包问题（acwing）<i class="fas fa-external-link-alt"></i></a></h2><p>有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。</p>
<p>第 i 种物品的体积是 vi，价值是 wi。</p>
<p>求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。<br>输出最大价值。</p>
<p><strong>输入格式</strong></p>
<p>第一行两个整数，N，V用空格隔开，分别表示物品种数和背包容积。</p>
<p>接下来有 N 行，每行两个整数 vi,wi用空格隔开，分别表示第 i 种物品的体积和价值。</p>
<p><strong>输出格式</strong></p>
<p>输出一个整数，表示最大价值。</p>
<p><strong>数据范围</strong></p>
<p>0&lt;N,V≤10000&lt;N,V≤1000<br>0&lt;vi,wi≤10000&lt;vi,wi≤1000</p>
<p><strong>输入样例</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="number">4</span> <span class="number">5</span></span><br><span class="line"><span class="number">1</span> <span class="number">2</span></span><br><span class="line"><span class="number">2</span> <span class="number">4</span></span><br><span class="line"><span class="number">3</span> <span class="number">4</span></span><br><span class="line"><span class="number">4</span> <span class="number">5</span></span><br></pre></td></tr></table></figure>

<p><strong>输出样例：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="number">10</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>相比01背包交换了内循环的顺序就ok了，当然也可以将每个物品拆分，不过复杂度会变高</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Main</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span></span>&#123;</span><br><span class="line">        Scanner sc=<span class="keyword">new</span> Scanner(System.in);</span><br><span class="line">        <span class="keyword">int</span> N=sc.nextInt();</span><br><span class="line">        <span class="keyword">int</span> V=sc.nextInt();</span><br><span class="line">        <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[V+<span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;N;i++)&#123;</span><br><span class="line">            <span class="keyword">int</span> vi=sc.nextInt();</span><br><span class="line">            <span class="keyword">int</span> wi=sc.nextInt();</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j=vi;j&lt;=V;j++) &#123;</span><br><span class="line">                dp[j]=Math.max(dp[j],dp[j-vi]+wi);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(dp[V]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其实这个结论要直接理解还是有点难懂的，具体的推导过程可以看下面的 <a href="#322-%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2">零钱兑换</a></p>
<h2 id="416-分割等和子集"><a href="#416-分割等和子集" class="headerlink" title="416. 分割等和子集"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/partition-equal-subset-sum/" >416. 分割等和子集<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。</p>
<p><strong>注意:</strong></p>
<ol>
<li>每个数组中的元素不会超过 100</li>
<li>数组的大小不会超过 200</li>
</ol>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>, <span class="number">5</span>, <span class="number">11</span>, <span class="number">5</span>]</span><br><span class="line"></span><br><span class="line">输出: <span class="keyword">true</span></span><br><span class="line"></span><br><span class="line">解释: 数组可以分割成 [<span class="number">1</span>, <span class="number">5</span>, <span class="number">5</span>] 和 [<span class="number">11</span>].</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入: [1, 2, 3, 5]</span><br><span class="line"></span><br><span class="line">输出: false</span><br><span class="line"></span><br><span class="line">解释: 数组不能分割成两个元素和相等的子集.</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>现在递归写起来已经有点感觉了，类似的题基本上都能写出记忆化递归的方法来</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//记忆化递归37ms 44%,开始慢是因为stream的原因</span></span><br><span class="line">Boolean[][] cache=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    <span class="comment">//int sum=Arrays.stream(nums).sum();</span></span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> e:nums) sum+=e; <span class="comment">//求和</span></span><br><span class="line">    cache=<span class="keyword">new</span> Boolean[nums.length][sum+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">if</span> (sum%<span class="number">2</span>!=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> partition(nums,<span class="number">0</span>,<span class="number">0</span>,sum/<span class="number">2</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//尝试添加[0,index]位置的元素,看能否使得half=sum (这里其实应该直接在sum上减,看能不能减为0)</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">partition</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> index,<span class="keyword">int</span> half,<span class="keyword">int</span> sum)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index==nums.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (cache[index][half]!=<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[index][half];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (half==sum) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    cache[index][half]=partition(nums,index+<span class="number">1</span>,half,sum) || </span><br><span class="line">        (half&lt;sum&amp;&amp;partition(nums,index+<span class="number">1</span>,half+nums[index],sum));</span><br><span class="line">    <span class="keyword">return</span> cache[index][half];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>动态规划，依然是典型的背包问题，可以理解为用nums中的元素，填满sum/2容量大小的背包，递推公式</p>
<p> <code>dp[i][j] =dp[i-1][j] || dp[i-1][j-nums[i]]</code>  选当前元素和不选当前元素，有一个能填满就ok</p>
<p><code>dp[i][j]</code> 含义为：考虑<code>[0,i]</code> 范围内的元素，能否恰好装满 <code>j</code>大小的容器</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//二维dp</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    <span class="comment">//int sum=Arrays.stream(nums).sum(); 用stream好慢</span></span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> e:nums) sum+=e; <span class="comment">//求和</span></span><br><span class="line">    <span class="keyword">if</span> (sum%<span class="number">2</span>!=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> half=sum/<span class="number">2</span>;</span><br><span class="line">    <span class="comment">//dp[i][j]的含义是从[0,i]中选取元素,能否刚好填满j</span></span><br><span class="line">    <span class="keyword">boolean</span>[][] dp=<span class="keyword">new</span> <span class="keyword">boolean</span>[nums.length][half+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=half;j++) &#123;</span><br><span class="line">        dp[<span class="number">0</span>][j]= nums[<span class="number">0</span>]==j;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=half;j++) &#123;</span><br><span class="line">            dp[i][j]= j&gt;=nums[i]?dp[i-<span class="number">1</span>][j] || dp[i-<span class="number">1</span>][j-nums[i]]:dp[i-<span class="number">1</span>][j];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果在某个位置（每行最后一个）已经刚好填满了就直接返回</span></span><br><span class="line">        <span class="keyword">if</span> (dp[i][half]) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[nums.length-<span class="number">1</span>][half];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>空间上的优化</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> e:nums) sum+=e; <span class="comment">//求和</span></span><br><span class="line">    <span class="keyword">if</span> (sum%<span class="number">2</span>!=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> half=sum/<span class="number">2</span>;</span><br><span class="line">    <span class="comment">//dp[j]的含义是从[0,i]中选取元素,能否刚好填满j</span></span><br><span class="line">    <span class="keyword">boolean</span>[] dp=<span class="keyword">new</span> <span class="keyword">boolean</span>[half+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=half;j++) &#123;</span><br><span class="line">        dp[j]= nums[<span class="number">0</span>]==j;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=half;j&gt;=nums[i];j--) &#123;</span><br><span class="line">            <span class="comment">//dp[i][j]= j&gt;=nums[i]?dp[i-1][j] || dp[i-1][j-nums[i]]:dp[i-1][j];</span></span><br><span class="line">            dp[j]=dp[j]||dp[j-nums[i]];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (dp[half]) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[half];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="322-零钱兑换"><a href="#322-零钱兑换" class="headerlink" title="322. 零钱兑换"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/coin-change/" >322. 零钱兑换<i class="fas fa-external-link-alt"></i></a></h2><p>给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: coins = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">5</span>], amount = <span class="number">11</span></span><br><span class="line">输出: <span class="number">3</span> </span><br><span class="line">解释: <span class="number">11</span> = <span class="number">5</span> + <span class="number">5</span> + <span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: coins = [<span class="number">2</span>], amount = <span class="number">3</span></span><br><span class="line">输出: -<span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong><br>你可以认为每种硬币的数量是无限的</p>
<p><strong>解法一</strong></p>
<p>其实就是dfs，我最开始就是写的dfs只不过时间复杂度太高，没做记忆化，这里其实一开始做了记忆化也一直没跑过，一直超时，最后给的case是6249 好像也不算很大吧，然后我后来把<code>fill</code> 填充数组删了，用Integer就跑过了。。。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//记忆化递归AC 50%左右</span></span><br><span class="line"><span class="keyword">private</span> Integer[] cache=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">coinChange2</span><span class="params">(<span class="keyword">int</span>[] coins,<span class="keyword">int</span> amount)</span></span>&#123;</span><br><span class="line">    cache=<span class="keyword">new</span> Integer[amount+<span class="number">1</span>];</span><br><span class="line">    <span class="comment">//Arrays.fill(cache,-1); 这里fill直接tle了。。。。</span></span><br><span class="line">    <span class="keyword">return</span> takeCoins(coins,amount);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">takeCoins</span><span class="params">(<span class="keyword">int</span>[] coins, <span class="keyword">int</span> amount)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (amount==<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (cache[amount]!=<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[amount];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//int t1=coins(coins,amount,index+1);</span></span><br><span class="line">    <span class="keyword">int</span> res=Integer.MAX_VALUE;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;coins.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (amount&lt;coins[i]) <span class="keyword">continue</span>;</span><br><span class="line">        <span class="keyword">int</span> sub=takeCoins(coins,amount-coins[i]);</span><br><span class="line">        <span class="keyword">if</span> (sub!=-<span class="number">1</span>) &#123;</span><br><span class="line">            res=Math.min(sub+<span class="number">1</span>,res);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    cache[amount]= res==Integer.MAX_VALUE?-<span class="number">1</span>:res;</span><br><span class="line">    <span class="keyword">return</span> cache[amount];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>动态规划，二维dp，注意这里其实和前面的背包问题就有区别了，这里实际上就是个<code>无限背包</code>问题，因为这里的硬币是无限的，每个面值的硬币都可以重复的选取</p>
<p><strong>DPTable</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200227/ekmjFAHgA2K4.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>状态定义</strong></p>
<p>这里<code>dp[i][j]</code> 的含义为：<strong>考虑<code>[0，i]</code> 范围内的元素，能凑成 <code>j</code> 所需的最少硬币数</strong>，和之前的01背包问题状态定义没什么区别</p>
<p><strong>状态方程</strong></p>
<p>首先明确一点，这里我们对第<code>coins[i]</code>个硬币有两种选择 </p>
<ol>
<li>不拿 </li>
<li> 拿，拿1~k个(k为硬币个数的限制，这里没有限制，所以是无穷大)</li>
</ol>
<p>进而我们可以的到状态转移的方程：</p>
<p><code>f[i][j] = min(f[i-1][j], f[i-1][j-c]+1, f[i-1][j-2*c]+2, ..., f[i-1][j-k*c]+k)</code></p>
<p>但是这个方程有很多计算是重复的</p>
<p><code>f[i][j-c]=min(f[i-1][j-c], f[i-1][j-2*c]+1, ..., f[i-1][j-k*c]+k-1)</code></p>
<p>两者合并得到</p>
<p><code>f[i][j] = min(f[i-1]f[j], f[i][j-c]+1)</code>  有了状态方程，代码就好写了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">coinChange4</span><span class="params">(<span class="keyword">int</span>[] coins,<span class="keyword">int</span> amount)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[][] dp=<span class="keyword">new</span> <span class="keyword">int</span>[coins.length][amount+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=amount;j++) &#123;</span><br><span class="line">        dp[<span class="number">0</span>][j]=j%coins[<span class="number">0</span>]==<span class="number">0</span>?j/coins[<span class="number">0</span>]:Integer.MAX_VALUE;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;coins.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=amount;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (j&lt;coins[i] || dp[i][j-coins[i]]==Integer.MAX_VALUE) &#123;</span><br><span class="line">                <span class="comment">//放不下</span></span><br><span class="line">                dp[i][j]=dp[i-<span class="number">1</span>][j];</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                dp[i][j]=Math.min(dp[i][j-coins[i]]+<span class="number">1</span>,dp[i-<span class="number">1</span>][j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[coins.length-<span class="number">1</span>][amount]!=Integer.MAX_VALUE?dp[coins.length-<span class="number">1</span>][amount]:-<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>空间优化</strong></p>
<p>将上面的二维改成一维就是像下面一样，注意内层的循环！因为后面是 <code>f[i][j-c]+1</code> 所以需要依赖同一层前面的结果，所以必须顺序的遍历</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">coinChange</span><span class="params">(<span class="keyword">int</span>[] coins,<span class="keyword">int</span> amount)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[amount+<span class="number">1</span>];</span><br><span class="line">    <span class="comment">//填充初始值为Integer.MAX_VALUE,代表不可达</span></span><br><span class="line">    Arrays.fill(dp,Integer.MAX_VALUE);</span><br><span class="line">    dp[<span class="number">0</span>]=<span class="number">0</span>; <span class="comment">//除了dp[0]</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;coins.length;i++) &#123;</span><br><span class="line">        <span class="comment">//注意这里不能逆序！</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=coins[i];j&lt;=amount;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (dp[j-coins[i]]!=Integer.MAX_VALUE) &#123;</span><br><span class="line">                dp[j]=Math.min(dp[j-coins[i]]+<span class="number">1</span>,dp[j]);   </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[amount]==Integer.MAX_VALUE?-<span class="number">1</span>:dp[amount];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="518-零钱兑换-II"><a href="#518-零钱兑换-II" class="headerlink" title="518. 零钱兑换 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/coin-change-2/" >518. 零钱兑换 II<i class="fas fa-external-link-alt"></i></a></h2><p>给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: amount = <span class="number">5</span>, coins = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">5</span>]</span><br><span class="line">输出: <span class="number">4</span></span><br><span class="line">解释: 有四种方式可以凑成总金额:</span><br><span class="line"><span class="number">5</span>=<span class="number">5</span></span><br><span class="line"><span class="number">5</span>=<span class="number">2</span>+<span class="number">2</span>+<span class="number">1</span></span><br><span class="line"><span class="number">5</span>=<span class="number">2</span>+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span></span><br><span class="line"><span class="number">5</span>=<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: amount = <span class="number">3</span>, coins = [<span class="number">2</span>]</span><br><span class="line">输出: <span class="number">0</span></span><br><span class="line">解释: 只用面额<span class="number">2</span>的硬币不能凑成总金额<span class="number">3</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: amount = <span class="number">10</span>, coins = [<span class="number">10</span>] </span><br><span class="line">输出: <span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong></p>
<p>你可以假设：</p>
<ul>
<li>0 &lt;= amount (总金额) &lt;= 5000</li>
<li>1 &lt;= coin (硬币面额) &lt;= 5000</li>
<li>硬币种类不超过 500 种</li>
<li>结果符合 32 位符号整数</li>
</ul>
<p><strong>解法一</strong></p>
<p>求方案数，不考虑顺序</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">change</span><span class="params">(<span class="keyword">int</span> amount, <span class="keyword">int</span>[] coins)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (coins==<span class="keyword">null</span> || coins.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> amount==<span class="number">0</span>?<span class="number">1</span>:<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[][] dp=<span class="keyword">new</span> <span class="keyword">int</span>[coins.length][amount+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;coins.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=amount;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (i==<span class="number">0</span>) &#123;</span><br><span class="line">                dp[<span class="number">0</span>][j]=j%coins[i]==<span class="number">0</span>?<span class="number">1</span>:<span class="number">0</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (j==<span class="number">0</span>) &#123;</span><br><span class="line">                dp[i][<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                  dp[i][j]= j&gt;=coins[i]?dp[i-<span class="number">1</span>][j]+dp[i][j-coins[i]]:dp[i-<span class="number">1</span>][j];</span><br><span class="line">                <span class="comment">//dp[i][j]= j&gt;=coins[i]?dp[i-1][j]+dp[i-1][j-coins[i]]:dp[i-1][j];</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[coins.length-<span class="number">1</span>][amount];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>空间优化</strong></p>
<p><code>f(5)=f(4)+f(3)+f(0)</code> 突然感觉写二维的有点多余。。。这种子结构要清晰的多</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//直接理解一维dp还是不太容易,但是知道递推公式后先写个二维dp再改为一维就很容易</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">change</span><span class="params">(<span class="keyword">int</span> amount, <span class="keyword">int</span>[] coins)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[amount+<span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//这种方式相当于对dpTable从左向右,一行行的递推</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;coins.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=amount;j++) &#123;</span><br><span class="line">            <span class="comment">//dp[j]+= dp[j-coins[i]]:0;</span></span><br><span class="line">            dp[j]=j-coins[i]&gt;=<span class="number">0</span>?dp[j]+dp[j-coins[i]]:dp[j];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/* 交换一下内外顺序就变成了另一个问题的解</span></span><br><span class="line"><span class="comment">    for (int j=0;j&lt;=amount;j++) &#123;</span></span><br><span class="line"><span class="comment">        for (int i=0;i&lt;coins.length;i++) &#123;</span></span><br><span class="line"><span class="comment">            dp[j]+= j-coins[i]&gt;=0?dp[j-coins[i]]:0;</span></span><br><span class="line"><span class="comment">        &#125;</span></span><br><span class="line"><span class="comment">    &#125;*/</span></span><br><span class="line">    <span class="keyword">return</span> dp[amount];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>记忆化递归，基本上dp能过得，记忆化递归一定能过，相比之下，我觉得记忆化递归会好写一些</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">change</span><span class="params">(<span class="keyword">int</span> amount, <span class="keyword">int</span>[] coins)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (coins==<span class="keyword">null</span> || coins.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> amount==<span class="number">0</span>?<span class="number">1</span>:<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    cache=<span class="keyword">new</span> Integer[coins.length][amount+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">return</span> takeCoins(amount,coins,<span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">Integer[][] cache=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">//[index,coins.length] 中凑成amount的方案数，考虑顺序</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">takeCoins</span><span class="params">(<span class="keyword">int</span> amount,<span class="keyword">int</span>[] coins,<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index&gt;=coins.length || amount&lt;<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (cache[index][amount]!=<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[index][amount];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (amount==<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> cache[index][amount]=takeCoins(amount-coins[index],coins,index)+takeCoins(amount,coins,index+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="面试题-08-11-硬币"><a href="#面试题-08-11-硬币" class="headerlink" title="面试题 08.11. 硬币"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/coin-lcci/" >面试题 08.11. 硬币<i class="fas fa-external-link-alt"></i></a></h2><p>硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)</p>
<p><strong>解法一</strong></p>
<p>和上面的一样的，但是这里有一些其他的方法，记录下，元素解法就不写了，和上面的一样</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">int</span> mod=<span class="number">1000000007</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">waysToChange</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    n/=<span class="number">5</span>; <span class="comment">//余数没有影响，都用1补</span></span><br><span class="line">    <span class="keyword">int</span>[] coins=&#123;<span class="number">5</span>,<span class="number">2</span>,<span class="number">1</span>&#125;; <span class="comment">//币值也/5</span></span><br><span class="line">    <span class="keyword">long</span>[] dp=<span class="keyword">new</span> <span class="keyword">long</span>[n+<span class="number">1</span>];</span><br><span class="line">    Arrays.fill(dp,<span class="number">1L</span>); <span class="comment">//排除1分的硬币，所有的面额都可以用1分的凑出来</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;coins.length;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=coins[i];j&lt;=n;j++)&#123;</span><br><span class="line">            dp[j]=(dp[j]+dp[j-coins[i]])%mod;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> (<span class="keyword">int</span>)(dp[n]%mod);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>直接把时间从114ms干到了17ms，其实时间复杂度没变，但是缩小了解空间，所以整体的时间会提高很多，当然这里能缩小的原因主要还是因为题目比较特殊</p>
<h2 id="377-组合总和-Ⅳ"><a href="#377-组合总和-Ⅳ" class="headerlink" title="377. 组合总和 Ⅳ"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/combination-sum-iv/" >377. 组合总和 Ⅳ<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">nums = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]</span><br><span class="line">target = <span class="number">4</span></span><br><span class="line"></span><br><span class="line">所有可能的组合为：</span><br><span class="line">(<span class="number">1</span>, <span class="number">1</span>, <span class="number">1</span>, <span class="number">1</span>)</span><br><span class="line">(<span class="number">1</span>, <span class="number">1</span>, <span class="number">2</span>)</span><br><span class="line">(<span class="number">1</span>, <span class="number">2</span>, <span class="number">1</span>)</span><br><span class="line">(<span class="number">1</span>, <span class="number">3</span>)</span><br><span class="line">(<span class="number">2</span>, <span class="number">1</span>, <span class="number">1</span>)</span><br><span class="line">(<span class="number">2</span>, <span class="number">2</span>)</span><br><span class="line">(<span class="number">3</span>, <span class="number">1</span>)</span><br><span class="line"></span><br><span class="line">请注意，顺序不同的序列被视作不同的组合。</span><br><span class="line"></span><br><span class="line">因此输出为 <span class="number">7</span>。</span><br></pre></td></tr></table></figure>

<p><strong>进阶：</strong><br>如果给定的数组中含有负数会怎么样？<br>问题会产生什么变化？<br>我们需要在题目中添加什么限制来允许负数的出现？</p>
<p><strong>解法一</strong></p>
<p>记忆化递归，没啥好说的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//记忆化递归 1ms 100%</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">combinationSum4</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    cache=<span class="keyword">new</span> Integer[target+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">return</span> combination(nums,target);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">Integer[] cache=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">combination</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> target)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (cache[target]!=<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[target];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (target==<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (target-nums[i]&gt;=<span class="number">0</span>) &#123;</span><br><span class="line">            res+=combination(nums,target-nums[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> cache[target]=res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>动态规划，乍一看好像和上面一题一样，实际上并不一样，这里是考虑顺序的，最优子结构也是</p>
<p><code>f(5)=f(4)+f(3)+f(0)</code> 这样的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//一维dp</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">combinationSum4</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> target)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[target+<span class="number">1</span>];</span><br><span class="line">    dp[<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;=target;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;nums.length;j++) &#123;</span><br><span class="line">            dp[i]+= i&gt;=nums[j]?dp[i-nums[j]]:<span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[target];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这里还是要存个疑啊，没搞明白啊，为啥交换个顺序就不一样了呢？一个是按行打表，一个是按列打表？？？还是递归好写。。。</p>
<h2 id="494-目标和"><a href="#494-目标和" class="headerlink" title="494. 目标和"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/target-sum/" >494. 目标和<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。</p>
<p>返回可以使最终数组和为目标数 S 的所有添加符号的方法数。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums: [<span class="number">1</span>, <span class="number">1</span>, <span class="number">1</span>, <span class="number">1</span>, <span class="number">1</span>], S: <span class="number">3</span></span><br><span class="line">输出: <span class="number">5</span></span><br><span class="line">解释: </span><br><span class="line"></span><br><span class="line">-<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span> = <span class="number">3</span></span><br><span class="line">+<span class="number">1</span>-<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span> = <span class="number">3</span></span><br><span class="line">+<span class="number">1</span>+<span class="number">1</span>-<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span> = <span class="number">3</span></span><br><span class="line">+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>-<span class="number">1</span>+<span class="number">1</span> = <span class="number">3</span></span><br><span class="line">+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>+<span class="number">1</span>-<span class="number">1</span> = <span class="number">3</span></span><br><span class="line"></span><br><span class="line">一共有<span class="number">5</span>种方法让最终目标和为<span class="number">3</span>。</span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong></p>
<ul>
<li>数组非空，且长度不会超过20。</li>
<li>初始的数组的和不会超过1000。</li>
<li>保证返回的最终结果能被32位整数存下</li>
</ul>
<p><strong>解法一</strong></p>
<p>后面的题都优先写记忆化递归了，动态规划确实有点难顶</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Integer[][] cache=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">//HashMap&lt;Integer,Integer&gt; cache=new HashMap&lt;&gt;</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findTargetSumWays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span> || S&gt;<span class="number">1000</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//</span></span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> n:nums)sum+=n;</span><br><span class="line">    <span class="keyword">if</span>(S&gt;sum)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">//相当于平移了一下,从[-sum,sum] --&gt; [0,2*sum]</span></span><br><span class="line">    cache=<span class="keyword">new</span> Integer[nums.length][<span class="number">2</span>*sum+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">return</span> findTarget(nums,S,<span class="number">0</span>,<span class="number">2</span>*sum+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findTarget</span><span class="params">(<span class="keyword">int</span>[] nums,<span class="keyword">int</span> S,<span class="keyword">int</span> index,<span class="keyword">int</span> max)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (S==<span class="number">0</span> &amp;&amp; index ==nums.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (index&gt;=nums.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(S &lt;<span class="number">0</span>  &amp;&amp; cache[index][S+max]!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> cache[index][S+max];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (S&gt;=<span class="number">0</span> &amp;&amp; cache[index][S]!=<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[index][S];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> temp=findTarget(nums,S-nums[index],index+<span class="number">1</span>,max)+findTarget(nums,S+nums[index],index+<span class="number">1</span>,max);</span><br><span class="line">    <span class="keyword">if</span> (S&lt;<span class="number">0</span>) &#123;</span><br><span class="line">        cache[index][S+max]=temp;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        cache[index][S]=temp;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>  temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这题还是挺有意思的，因为里面是有负数的，直接记忆化是不行的，需要转换一下，这里我是直接将cache数组扩大，同时保证不会有覆盖，所以直接扩大为 2sum就ok，这样整个S的范围就从<code>[-sum,+sum]</code> 变为 <code>[0,2sum]</code> 从而可以缓存所有的递归结果，其实也可以使用两个数组一个存正数，一个存负数，然后只需要符号取反就ok了，只不过占用的空间会大一点</p>
<p><strong>解法二</strong></p>
<p>正儿八经的01背包做法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findTargetSumWays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="comment">//nsum负,psum正; sum;</span></span><br><span class="line">    <span class="comment">//sum=psum+nsum;</span></span><br><span class="line">    <span class="comment">//S=psum-nsum;</span></span><br><span class="line">    <span class="comment">//(sum+S)/2 = psum</span></span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) sum+=nums[i];</span><br><span class="line">    <span class="keyword">if</span>((sum+S)%<span class="number">2</span>!=<span class="number">0</span> || S&gt;sum) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> target=(sum+S)/<span class="number">2</span>;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[target+<span class="number">1</span>];</span><br><span class="line">    <span class="comment">//Arrays.fill(dp,-1);</span></span><br><span class="line">    dp[<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=target;j&gt;=nums[i];j--)&#123;</span><br><span class="line">            dp[j]+=dp[j-nums[i]];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[target];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1049-最后一块石头的重量-II"><a href="#1049-最后一块石头的重量-II" class="headerlink" title="1049. 最后一块石头的重量 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/last-stone-weight-ii/" >1049. 最后一块石头的重量 II<i class="fas fa-external-link-alt"></i></a></h2><p>有一堆石头，每块石头的重量都是正整数。</p>
<p>每一回合，从中选出<strong>任意两块石头</strong>，然后将它们一起粉碎。假设石头的重量分别为 <code>x</code> 和 <code>y</code>，且 <code>x &lt;= y</code>。那么粉碎的可能结果如下：</p>
<ul>
<li>如果 <code>x == y</code>，那么两块石头都会被完全粉碎；</li>
<li>如果 <code>x != y</code>，那么重量为 <code>x</code> 的石头将会完全粉碎，而重量为 <code>y</code> 的石头新重量为 <code>y-x</code>。</li>
</ul>
<p>最后，最多只会剩下一块石头。返回此石头<strong>最小的可能重量</strong>。如果没有石头剩下，就返回 <code>0</code>。</p>
<p><strong>示例：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">2</span>,<span class="number">7</span>,<span class="number">4</span>,<span class="number">1</span>,<span class="number">8</span>,<span class="number">1</span>]</span><br><span class="line">输出：<span class="number">1</span></span><br><span class="line">解释：</span><br><span class="line">组合 <span class="number">2</span> 和 <span class="number">4</span>，得到 <span class="number">2</span>，所以数组转化为 [<span class="number">2</span>,<span class="number">7</span>,<span class="number">1</span>,<span class="number">8</span>,<span class="number">1</span>]，</span><br><span class="line">组合 <span class="number">7</span> 和 <span class="number">8</span>，得到 <span class="number">1</span>，所以数组转化为 [<span class="number">2</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>]，</span><br><span class="line">组合 <span class="number">2</span> 和 <span class="number">1</span>，得到 <span class="number">1</span>，所以数组转化为 [<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>]，</span><br><span class="line">组合 <span class="number">1</span> 和 <span class="number">1</span>，得到 <span class="number">0</span>，所以数组转化为 [<span class="number">1</span>]，这就是最优值。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= stones.length &lt;= 30</code></li>
<li><code>1 &lt;= stones[i] &lt;= 1000</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>想了一下，其实就是在所有石头中选取部分石头，求这部分的石头和大于<code>sum/2</code>的最小值（和正常的背包思路反着来的）</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//   sum   = psum + nsum</span></span><br><span class="line"><span class="comment">//  target = psum - nsum  (psum &gt;= nsum)</span></span><br><span class="line"><span class="comment">//  sum+target = 2*psum</span></span><br><span class="line"><span class="comment">//  target = 2*psum-sum</span></span><br><span class="line"><span class="comment">//  2*psum-sum&gt;=0</span></span><br><span class="line"><span class="comment">//记忆化递归</span></span><br><span class="line">Integer[][] dp=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lastStoneWeightII</span><span class="params">(<span class="keyword">int</span>[] stones)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;stones.length;i++) &#123;</span><br><span class="line">        sum+=stones[i];</span><br><span class="line">    &#125;</span><br><span class="line">    dp=<span class="keyword">new</span> Integer[stones.length+<span class="number">1</span>][sum];</span><br><span class="line">    <span class="keyword">return</span> <span class="number">2</span>*dfs(stones,<span class="number">0</span>,<span class="number">0</span>,sum)-sum;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span>[] stones,<span class="keyword">int</span> index,<span class="keyword">int</span> psum,<span class="keyword">int</span> sum)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="number">2</span>*psum&gt;=sum)&#123;</span><br><span class="line">        <span class="keyword">return</span> psum;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(dp[index][psum]!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> dp[index][psum];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> min=Integer.MAX_VALUE;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=index;i&lt;stones.length;i++) &#123;</span><br><span class="line">        min=Math.min(dfs(stones,i+<span class="number">1</span>,psum+stones[i],sum),min);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[index][psum]=min;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>当我按照这个思路i写出来后发现不好改递推了😂，这个思路确实有一点点怪</p>
<p><strong>解法二</strong></p>
<p>正常的01背包解法，其实把上面的结论反过来就行了，既然要求一个大于等于<code>sum/2</code>的最小值，其实就是求一个小于等于<code>sum/2</code> 的最大值，这样一说就很清楚了，经典的01背包</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lastStoneWeightII</span><span class="params">(<span class="keyword">int</span>[] stones)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(stones==<span class="keyword">null</span> ||stones.length&lt;=<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> n=stones.length;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)&#123;</span><br><span class="line">        sum+=stones[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//背包容量为sum/2,求最多能装多少,经典的01背包</span></span><br><span class="line">    <span class="keyword">int</span> amount=sum/<span class="number">2</span>;</span><br><span class="line">    <span class="keyword">int</span>[] dp=<span class="keyword">new</span> <span class="keyword">int</span>[amount+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;stones.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=amount;j&gt;=stones[i];j--) &#123;</span><br><span class="line">            dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//wrong: return (amount-dp[amount])*2;</span></span><br><span class="line">    <span class="comment">//return sum%2==0?(amount-dp[amount])*2:(amount-dp[amount])*2+1</span></span><br><span class="line">    <span class="comment">//nsum=dp[amount]</span></span><br><span class="line">    <span class="comment">//target=psum-nsum = sum-nusm-nsum</span></span><br><span class="line">    <span class="keyword">return</span> sum-<span class="number">2</span>*dp[amount];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里的retrun有两种写法，推荐第二种，第一种还要判奇偶</p>
<blockquote>
<p>拿到这题的的第一个解法其实是贪心，每次消除两个最大的，用优先队列维护石头大小</p>
<p>天真的错误解法 74 / 82 个通过测试用例<br>[21,26,31,33,40] -&gt;[7,21,26,31] -&gt; [5,7,21] -&gt; [5,14] -&gt;[9]<br>[21,26,31,33,40] -&gt;[19,26,31,33]-&gt;[5]</p>
<p>这个思路其实是 这题的弱化版本 <a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/last-stone-weight/" >1046. 最后一块石头的重量<i class="fas fa-external-link-alt"></i></a> 的解法</p>
</blockquote>
<h2 id="474-一和零"><a href="#474-一和零" class="headerlink" title="474. 一和零"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/ones-and-zeroes/" >474. 一和零<i class="fas fa-external-link-alt"></i></a></h2><p>在计算机界中，我们总是追求用有限的资源获取最大的收益。</p>
<p>现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。</p>
<p>你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。</p>
<p><strong>注意:</strong></p>
<ul>
<li>给定 0 和 1 的数量都不会超过 100。</li>
<li>给定字符串数组的长度不会超过 600。</li>
</ul>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: Array = &#123;<span class="string">&quot;10&quot;</span>, <span class="string">&quot;0001&quot;</span>, <span class="string">&quot;111001&quot;</span>, <span class="string">&quot;1&quot;</span>, <span class="string">&quot;0&quot;</span>&#125;, m = <span class="number">5</span>, n = <span class="number">3</span></span><br><span class="line">输出: <span class="number">4</span></span><br><span class="line"></span><br><span class="line">解释: 总共 <span class="number">4</span> 个字符串可以通过 <span class="number">5</span> 个 <span class="number">0</span> 和 <span class="number">3</span> 个 <span class="number">1</span> 拼出，即 <span class="string">&quot;10&quot;</span>,<span class="string">&quot;0001&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;0&quot;</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: Array = &#123;<span class="string">&quot;10&quot;</span>, <span class="string">&quot;0&quot;</span>, <span class="string">&quot;1&quot;</span>&#125;, m = <span class="number">1</span>, n = <span class="number">1</span></span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line"></span><br><span class="line">解释: 你可以拼出 <span class="string">&quot;10&quot;</span>，但之后就没有剩余数字了。更好的选择是拼出 <span class="string">&quot;0&quot;</span> 和 <span class="string">&quot;1&quot;</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>之前只用Java写了个记忆化的，补一下纯dp的</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">//之前只用Java写了个记忆化的，补一下纯dp的</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">findMaxForm</span><span class="params">(strs []<span class="keyword">string</span>, m <span class="keyword">int</span>, n <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> sn = <span class="built_in">len</span>(strs)</span><br><span class="line">    <span class="keyword">var</span> dp = <span class="built_in">make</span>([][]<span class="keyword">int</span>, m+<span class="number">1</span>)</span><br><span class="line">    <span class="keyword">var</span> Max = <span class="function"><span class="keyword">func</span><span class="params">(a, b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;<span class="keyword">if</span> a&gt;b &#123;<span class="keyword">return</span> a&#125;;<span class="keyword">return</span> b&#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt;= m; i++ &#123;</span><br><span class="line">        dp[i] = <span class="built_in">make</span>([]<span class="keyword">int</span>, n+<span class="number">1</span>)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; sn; i++ &#123;</span><br><span class="line">        zero, one := count(strs[i])</span><br><span class="line">        <span class="keyword">for</span> j := m; j &gt;= zero; j-- &#123;</span><br><span class="line">            <span class="keyword">for</span> k := n; k &gt;= one; k-- &#123;</span><br><span class="line">                dp[j][k] = Max(dp[j][k], dp[j-zero][k-one]+<span class="number">1</span>)</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[m][n]</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">count</span><span class="params">(str <span class="keyword">string</span>)</span> <span class="params">(<span class="keyword">int</span>, <span class="keyword">int</span>)</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> one, zero = <span class="number">0</span>, <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; <span class="built_in">len</span>(str); i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> str[i] == <span class="string">&#x27;0&#x27;</span> &#123;</span><br><span class="line">            zero++</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> str[i] == <span class="string">&#x27;1&#x27;</span> &#123;</span><br><span class="line">            one++</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> zero, one</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>其实这是一个多重背包问题，一个物品有多个权值</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Integer [][][] cache=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMaxForm</span><span class="params">(String[] strs, <span class="keyword">int</span> m, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    cache=<span class="keyword">new</span> Integer[m+<span class="number">1</span>][n+<span class="number">1</span>][strs.length];</span><br><span class="line">    <span class="keyword">return</span> findMax(strs,m,n,<span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//m:0 n:1</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMax</span><span class="params">(String[] strs, <span class="keyword">int</span> m, <span class="keyword">int</span> n,<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index&gt;=strs.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (cache[m][n][index]!=<span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[m][n][index];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] oz=count(strs[index]);</span><br><span class="line">    <span class="keyword">if</span> (oz[<span class="number">1</span>]&lt;=n &amp;&amp; oz[<span class="number">0</span>]&lt;=m) &#123;</span><br><span class="line">        <span class="keyword">return</span> cache[m][n][index]=Math.max(<span class="number">1</span>+findMax(strs,m-oz[<span class="number">0</span>],n-oz[<span class="number">1</span>],index+<span class="number">1</span>),findMax(strs,m,n,index+<span class="number">1</span>));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> cache[m][n][index]=findMax(strs,m,n,index+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] count(String str)&#123;</span><br><span class="line">    <span class="keyword">int</span> one=<span class="number">0</span>,zero=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">char</span>[] s=str.toCharArray();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">char</span> c:s) &#123;</span><br><span class="line">        <span class="keyword">if</span> (c==<span class="string">&#x27;1&#x27;</span>) &#123;</span><br><span class="line">            one++;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            zero++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;zero,one&#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1255-得分最高的单词集合"><a href="#1255-得分最高的单词集合" class="headerlink" title="1255. 得分最高的单词集合"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-score-words-formed-by-letters/" >1255. 得分最高的单词集合<i class="fas fa-external-link-alt"></i></a></h2><p>你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。</p>
<p>请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。</p>
<p>单词拼写游戏的规则概述如下：</p>
<ul>
<li>玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。</li>
<li>可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。</li>
<li>单词表 words 中每个单词只能计分（使用）一次。</li>
<li>根据字母得分情况表score，字母 ‘a’, ‘b’, ‘c’, … , ‘z’ 对应的得分分别为 score[0], score[1], …, score[25]。</li>
<li>本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和</li>
</ul>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：words = [<span class="string">&quot;dog&quot;</span>,<span class="string">&quot;cat&quot;</span>,<span class="string">&quot;dad&quot;</span>,<span class="string">&quot;good&quot;</span>], letters = [<span class="string">&quot;a&quot;</span>,<span class="string">&quot;a&quot;</span>,<span class="string">&quot;c&quot;</span>,<span class="string">&quot;d&quot;</span>,<span class="string">&quot;d&quot;</span>,<span class="string">&quot;d&quot;</span>,<span class="string">&quot;g&quot;</span>,<span class="string">&quot;o&quot;</span>,<span class="string">&quot;o&quot;</span>], score = [<span class="number">1</span>,<span class="number">0</span>,<span class="number">9</span>,<span class="number">5</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">2</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]</span><br><span class="line">输出：<span class="number">23</span></span><br><span class="line">解释：</span><br><span class="line">字母得分为  a=<span class="number">1</span>, c=<span class="number">9</span>, d=<span class="number">5</span>, g=<span class="number">3</span>, o=<span class="number">2</span></span><br><span class="line">使用给定的字母表 letters，我们可以拼写单词 <span class="string">&quot;dad&quot;</span> (<span class="number">5</span>+<span class="number">1</span>+<span class="number">5</span>)和 <span class="string">&quot;good&quot;</span> (<span class="number">3</span>+<span class="number">2</span>+<span class="number">2</span>+<span class="number">5</span>)，得分为 <span class="number">23</span> 。</span><br><span class="line">而单词 <span class="string">&quot;dad&quot;</span> 和 <span class="string">&quot;dog&quot;</span> 只能得到 <span class="number">21</span> 分。</span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：words = [<span class="string">&quot;xxxz&quot;</span>,<span class="string">&quot;ax&quot;</span>,<span class="string">&quot;bx&quot;</span>,<span class="string">&quot;cx&quot;</span>], letters = [<span class="string">&quot;z&quot;</span>,<span class="string">&quot;a&quot;</span>,<span class="string">&quot;b&quot;</span>,<span class="string">&quot;c&quot;</span>,<span class="string">&quot;x&quot;</span>,<span class="string">&quot;x&quot;</span>,<span class="string">&quot;x&quot;</span>], score = [<span class="number">4</span>,<span class="number">4</span>,<span class="number">4</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">5</span>,<span class="number">0</span>,<span class="number">10</span>]</span><br><span class="line">输出：<span class="number">27</span></span><br><span class="line">解释：</span><br><span class="line">字母得分为  a=<span class="number">4</span>, b=<span class="number">4</span>, c=<span class="number">4</span>, x=<span class="number">5</span>, z=<span class="number">10</span></span><br><span class="line">使用给定的字母表 letters，我们可以组成单词 <span class="string">&quot;ax&quot;</span> (<span class="number">4</span>+<span class="number">5</span>)， <span class="string">&quot;bx&quot;</span> (<span class="number">4</span>+<span class="number">5</span>) 和 <span class="string">&quot;cx&quot;</span> (<span class="number">4</span>+<span class="number">5</span>) ，总得分为 <span class="number">27</span> 。</span><br><span class="line">单词 <span class="string">&quot;xxxz&quot;</span> 的得分仅为 <span class="number">25</span> 。</span><br></pre></td></tr></table></figure>


<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：words = [<span class="string">&quot;leetcode&quot;</span>], letters = [<span class="string">&quot;l&quot;</span>,<span class="string">&quot;e&quot;</span>,<span class="string">&quot;t&quot;</span>,<span class="string">&quot;c&quot;</span>,<span class="string">&quot;o&quot;</span>,<span class="string">&quot;d&quot;</span>], score = [<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]</span><br><span class="line">输出：<span class="number">0</span></span><br><span class="line">解释：</span><br><span class="line">字母 <span class="string">&quot;e&quot;</span> 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= words.length &lt;= 14</code></li>
<li><code>1 &lt;= words[i].length &lt;= 15</code></li>
<li><code>1 &lt;= letters.length &lt;= 100</code></li>
<li><code>letters[i].length == 1</code></li>
<li><code>score.length == 26</code></li>
<li><code>0 &lt;= score[i] &lt;= 10</code></li>
<li><code>words[i] 和 letters[i] </code>只包含小写的英文字母</li>
</ul>
<p><strong>解法一</strong></p>
<p>看着题目就知道这题不简单😂，11.10的周赛最后一题，1ms，用01背包的思路做的，很多地方其实还没处理好</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxScoreWords</span><span class="params">(String[] words, <span class="keyword">char</span>[] letters, <span class="keyword">int</span>[] score)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] les=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">26</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;letters.length;i++) &#123;</span><br><span class="line">        les[letters[i]-<span class="string">&#x27;a&#x27;</span>]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> maxScoreWords(words,letters,score,<span class="number">0</span>,les);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxScoreWords</span><span class="params">(String[] words, <span class="keyword">char</span>[] letters, <span class="keyword">int</span>[] score,<span class="keyword">int</span> index,<span class="keyword">int</span>[] les)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index==words.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=maxScoreWords(words,letters,score,index+<span class="number">1</span>,les);</span><br><span class="line">    String word=words[index];</span><br><span class="line">    <span class="keyword">if</span> (hasWord(les,word)) &#123;</span><br><span class="line">        <span class="keyword">int</span>[] bak=<span class="keyword">new</span> <span class="keyword">int</span>[les.length];</span><br><span class="line">        System.arraycopy(les,<span class="number">0</span>,bak,<span class="number">0</span>,les.length);</span><br><span class="line">        res=Math.max(res,getScore(bak,word,score)+maxScoreWords(words,letters,score,index+<span class="number">1</span>,bak));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasWord</span><span class="params">(<span class="keyword">int</span>[] les,String word)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] bak=<span class="keyword">new</span> <span class="keyword">int</span>[les.length];</span><br><span class="line">    System.arraycopy(les,<span class="number">0</span>,bak,<span class="number">0</span>,les.length);</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">char</span> c:word.toCharArray())&#123;</span><br><span class="line">        <span class="keyword">if</span> (bak[c-<span class="string">&#x27;a&#x27;</span>]!=<span class="number">0</span>) &#123;</span><br><span class="line">            bak[c-<span class="string">&#x27;a&#x27;</span>]--;</span><br><span class="line">            count++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count==word.length();</span><br><span class="line">&#125;   </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getScore</span><span class="params">(<span class="keyword">int</span>[] les,String word,<span class="keyword">int</span>[] score)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> sc=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">char</span> c:word.toCharArray()) &#123;</span><br><span class="line">        les[c-<span class="string">&#x27;a&#x27;</span>]--;</span><br><span class="line">        sc+=score[c-<span class="string">&#x27;a&#x27;</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sc;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="HUD4501-小明系列故事——买年货（HUDOJ）"><a href="#HUD4501-小明系列故事——买年货（HUDOJ）" class="headerlink" title="HUD4501.小明系列故事——买年货（HUDOJ）"></a><a class="link"   target="_blank" rel="noopener" href="http://acm.hdu.edu.cn/showproblem.php?pid=4501" >HUD4501.小明系列故事——买年货（HUDOJ）<i class="fas fa-external-link-alt"></i></a></h2><p><strong>Problem Description</strong></p>
<p>春节将至，小明要去超市购置年货，于是小明去了自己经常去的都尚超市。</p>
<p>刚到超市，小明就发现超市门口聚集一堆人。用白云女士的话说就是：“那家伙，那场面，真是人山人海，锣鼓喧天，鞭炮齐呤，红旗招展。那可真是相当的壮观啊！”。好奇的小明走过去，奋力挤过人群，发现超市门口贴了一张通知，内容如下</p>
<p>值此新春佳节来临之际，为了回馈广大顾客的支持和厚爱，特举行春节大酬宾、优惠大放送活动。凡是都尚会员都可用会员积分兑换商品，凡是都尚会员都可<strong>免费拿k件商品</strong>，凡是购物顾客均有好礼相送。满100元送bla bla bla bla，满200元送bla bla bla bla bla…blablabla….</p>
<p>还没看完通知，小明就高兴的要死，因为他就是都尚的会员啊。迫不及待的小明在超市逛了一圈发现超市里有<strong>n件他想要的商品</strong>。小明顺便对这n件商品打了分，表示商品的实际价值。小明发现身上带了<strong>v1的人民币</strong>，会员卡里面有<strong>v2的积分</strong>。他想知道他最多能买多大价值的商品。</p>
<p>由于小明想要的商品实在太多了，他算了半天头都疼了也没算出来，所以请你这位聪明的程序员来帮帮他吧。</p>
<p><strong>Input</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入包含多组测试用例。</span><br><span class="line">每组数据的第一行是四个整数n，v1，v2，k；</span><br><span class="line">然后是n行，每行三个整数a，b，val，分别表示每个商品的价钱，兑换所需积分，实际价值。</span><br><span class="line">[Technical Specification]</span><br><span class="line"><span class="number">1</span> &lt;= n &lt;= <span class="number">100</span></span><br><span class="line"><span class="number">0</span> &lt;= v1, v2 &lt;= <span class="number">100</span></span><br><span class="line"><span class="number">0</span> &lt;= k &lt;= <span class="number">5</span></span><br><span class="line"><span class="number">0</span> &lt;= a, b, val &lt;= <span class="number">100</span></span><br><span class="line"></span><br><span class="line">Ps. 只要钱或者积分满足购买一件商品的要求，那么就可以买下这件商品。</span><br></pre></td></tr></table></figure>

<p><strong>Output</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">对于每组数据，输出能买的最大价值。</span><br><span class="line">详细信息见Sample。</span><br></pre></td></tr></table></figure>
<p><strong>Sample Input</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"><span class="number">5</span> <span class="number">1</span> <span class="number">6</span> <span class="number">1</span></span><br><span class="line"><span class="number">4</span> <span class="number">3</span> <span class="number">3</span></span><br><span class="line"><span class="number">0</span> <span class="number">3</span> <span class="number">2</span></span><br><span class="line"><span class="number">2</span> <span class="number">3</span> <span class="number">3</span></span><br><span class="line"><span class="number">3</span> <span class="number">3</span> <span class="number">2</span></span><br><span class="line"><span class="number">1</span> <span class="number">0</span> <span class="number">2</span></span><br><span class="line"><span class="number">4</span> <span class="number">2</span> <span class="number">5</span> <span class="number">0</span></span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">0</span></span><br><span class="line"><span class="number">4</span> <span class="number">4</span> <span class="number">1</span></span><br><span class="line"><span class="number">3</span> <span class="number">3</span> <span class="number">4</span></span><br><span class="line"><span class="number">3</span> <span class="number">4</span> <span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>Sample Output</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"><span class="number">12</span></span><br><span class="line"><span class="number">4</span></span><br></pre></td></tr></table></figure>
<p>Source<br>2013腾讯编程马拉松初赛第〇场（3月20日）</p>
<p><strong>解法一</strong></p>
<p>三维费用的背包，但是和前面的<a href="#474-%E4%B8%80%E5%92%8C%E9%9B%B6">474.一和零</a>还有点不一样，三个维度的费用是无关的，而1和0中1的个数和0的个数是相关的</p>
<blockquote>
<p>代码使用了Petr的输入模板，自己改进了下，增加了输入结束判断，所以看起来特别长</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"><span class="keyword">import</span> java.io.*;<span class="comment">// petr的输入模板</span></span><br><span class="line"><span class="keyword">import</span> java.math.*; <span class="comment">// 不是大数题可以不要这个</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solve_HDOJ_4501</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> PrintWriter out = <span class="keyword">new</span> PrintWriter(<span class="keyword">new</span> OutputStreamWriter(System.out));</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> Exception</span>&#123;</span><br><span class="line">        InputReader in = <span class="keyword">new</span> InputReader(System.in);</span><br><span class="line">        <span class="comment">//InputReader in = new InputReader(new FileInputStream(&quot;./input.txt&quot;));</span></span><br><span class="line">        <span class="keyword">while</span>(!in.EOF()) &#123;</span><br><span class="line">            <span class="keyword">int</span> n = in.nextInt();</span><br><span class="line">            <span class="keyword">int</span> v1 = in.nextInt();</span><br><span class="line">            <span class="keyword">int</span> v2 = in.nextInt();</span><br><span class="line">            <span class="keyword">int</span> k = in.nextInt();</span><br><span class="line">            <span class="keyword">int</span>[][] cost = <span class="keyword">new</span> <span class="keyword">int</span>[n][<span class="number">3</span>];</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">                cost[i][<span class="number">0</span>] = in.nextInt();</span><br><span class="line">                cost[i][<span class="number">1</span>] = in.nextInt();</span><br><span class="line">                cost[i][<span class="number">2</span>] = in.nextInt();</span><br><span class="line">            &#125;</span><br><span class="line">            solve(n, v1, v2, k, cost);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//别忘了flush</span></span><br><span class="line">        out.flush();</span><br><span class="line">        out.close();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//因为数据量不大，就直接Scanner了</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">solve</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> v1, <span class="keyword">int</span> v2, <span class="keyword">int</span> k, <span class="keyword">int</span>[][] cost)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span>[][][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[k+<span class="number">1</span>][v1+<span class="number">1</span>][v2+<span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = k; j &gt;= <span class="number">0</span>; j--) &#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> u = v1; u &gt;= <span class="number">0</span>; u--) &#123;</span><br><span class="line">                    <span class="keyword">for</span> (<span class="keyword">int</span> w = v2; w &gt;= <span class="number">0</span>; w--) &#123;</span><br><span class="line">                        <span class="comment">//这里不能直接u&gt;=cost[i][0] w &gt;= cost[i][1]，因为积分和钱和免费拿是分开的，没有关联的</span></span><br><span class="line">                        <span class="comment">//即使我不能免费拿，但是我能用积分拿，即使不能用积分拿，我可以用钱买</span></span><br><span class="line">                        <span class="comment">//dp[j][u][w] = Math.max(dp[j][u][w], dp[j-1][u-cost[i][0]][w-cost[i][1]] + cost[i][2]);</span></span><br><span class="line">                        <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line">                        <span class="keyword">if</span> (j &gt;= <span class="number">1</span>) &#123; <span class="comment">//免费拿</span></span><br><span class="line">                            ans = Math.max(ans, dp[j-<span class="number">1</span>][u][w] + cost[i][<span class="number">2</span>]);</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="keyword">if</span> (u &gt;= cost[i][<span class="number">0</span>]) &#123; <span class="comment">//钱</span></span><br><span class="line">                            ans = Math.max(ans, dp[j][u-cost[i][<span class="number">0</span>]][w] + cost[i][<span class="number">2</span>]);</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="keyword">if</span> (w &gt;= cost[i][<span class="number">1</span>]) &#123; <span class="comment">//积分</span></span><br><span class="line">                            ans = Math.max(ans, dp[j][u][w-cost[i][<span class="number">1</span>]] + cost[i][<span class="number">2</span>]);</span><br><span class="line">                        &#125;</span><br><span class="line">                        dp[j][u][w] = Math.max(ans, dp[j][u][w]);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        out.println(dp[k][v1][v2]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">InputReader</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> BufferedReader reader;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">public</span> StringTokenizer tokenizer;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">InputReader</span><span class="params">(InputStream stream)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//char[32768]</span></span><br><span class="line">        reader = <span class="keyword">new</span> BufferedReader(<span class="keyword">new</span> InputStreamReader(stream), <span class="number">32768</span>);</span><br><span class="line">        tokenizer = <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//默认以&quot; &quot;作为分隔符，读一个</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> String <span class="title">next</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">while</span> (tokenizer == <span class="keyword">null</span> || !tokenizer.hasMoreTokens()) &#123;</span><br><span class="line">            <span class="keyword">try</span> &#123;</span><br><span class="line">                tokenizer = <span class="keyword">new</span> StringTokenizer(reader.readLine());</span><br><span class="line">            &#125; <span class="keyword">catch</span> (IOException e) &#123;</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(e);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> tokenizer.nextToken();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//有的题目不给有多少组测试用例，只能一直读，读到结尾，需要自己判断结束</span></span><br><span class="line">    <span class="comment">//该函数也会读取一行，并初始化tokenizer，后序直接nextInt..等就可以读到该行</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">EOF</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        String str = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">try</span> &#123;</span><br><span class="line">            str = reader.readLine();</span><br><span class="line">            <span class="keyword">if</span> (str == <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//创建tokenizer</span></span><br><span class="line">            tokenizer = <span class="keyword">new</span> StringTokenizer(str);</span><br><span class="line">        &#125; <span class="keyword">catch</span> (IOException e) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(e);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">nextInt</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> Integer.parseInt(next());</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">long</span> <span class="title">nextLong</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> Long.parseLong(next());</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">double</span> <span class="title">nextDouble</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> Double.parseDouble(next());</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function">BigInteger <span class="title">nextBigInteger</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> BigInteger(next());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function">BigDecimal <span class="title">nextBigDecimal</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> BigDecimal(next());</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：LeetCode背包问题</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2019-11-29 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2019/11/29/f68a53d9/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2019/12/01/4bb85ba2/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">堆和优先队列</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2019/11/25/96f168ad/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Map映射结构</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2019/11/29/f68a53d9/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#92-%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%EF%BC%88lintCode%EF%BC%89"><span class="nav-number">1.</span> <span class="nav-text">92.背包问题（lintCode）</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%EF%BC%88acwing%EF%BC%89"><span class="nav-number">2.</span> <span class="nav-text">完全背包问题（acwing）</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#416-%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86"><span class="nav-number">3.</span> <span class="nav-text">416. 分割等和子集</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#322-%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2"><span class="nav-number">4.</span> <span class="nav-text">322. 零钱兑换</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#518-%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2-II"><span class="nav-number">5.</span> <span class="nav-text">518. 零钱兑换 II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%9D%A2%E8%AF%95%E9%A2%98-08-11-%E7%A1%AC%E5%B8%81"><span class="nav-number">6.</span> <span class="nav-text">面试题 08.11. 硬币</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#377-%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C-%E2%85%A3"><span class="nav-number">7.</span> <span class="nav-text">377. 组合总和 Ⅳ</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#494-%E7%9B%AE%E6%A0%87%E5%92%8C"><span class="nav-number">8.</span> <span class="nav-text">494. 目标和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1049-%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8F-II"><span class="nav-number">9.</span> <span class="nav-text">1049. 最后一块石头的重量 II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#474-%E4%B8%80%E5%92%8C%E9%9B%B6"><span class="nav-number">10.</span> <span class="nav-text">474. 一和零</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1255-%E5%BE%97%E5%88%86%E6%9C%80%E9%AB%98%E7%9A%84%E5%8D%95%E8%AF%8D%E9%9B%86%E5%90%88"><span class="nav-number">11.</span> <span class="nav-text">1255. 得分最高的单词集合</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#HUD4501-%E5%B0%8F%E6%98%8E%E7%B3%BB%E5%88%97%E6%95%85%E4%BA%8B%E2%80%94%E2%80%94%E4%B9%B0%E5%B9%B4%E8%B4%A7%EF%BC%88HUDOJ%EF%BC%89"><span class="nav-number">12.</span> <span class="nav-text">HUD4501.小明系列故事——买年货（HUDOJ）</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
